A stream of video data to be encoded is illustrated schematically in FIG. 1a. The stream comprises multiple frames (F) each representing the video image at a different respective moment in time. As will be familiar to a person skilled in the art, for the purpose of encoding, each frame (F) is divided into portions and each portion may also be subdivided into smaller sub-portions, each portion or sub-portion comprising a plurality of pixels. For example, according to one terminology each frame of a video stream to be encoded is divided into macroblocks (MB) and each macroblock is sub-divided into blocks or subblocks (b), each block or subblock comprising multiple pixels. Each frame may also be divided into independently decodable slices (S), each slice comprising one or more macroblocks. N.B. the divisions shown in FIG. 1a are only schematic for illustrative purposes and it will be appreciated that these are not necessarily meant to correspond to any actual encoding scheme—e.g. each frame is likely to contain a larger number of macroblocks.
A goal of a video codec is to reduce the bit rate needed to transmit a video signal, while maintaining highest possible quality. This goal is achieved by exploiting statistical redundancies (similarities in the video signal) and perceptual irrelevancies (related to sensitivity of human visual system).
Most of today's video codecs are based on an architecture that includes prediction of pixel blocks from other pixel blocks, transform of prediction residuals, quantization of transform coefficients, and entropy coding of quantization indices. These steps contribute to reducing redundancies and irrelevancies.
The prediction can typically be performed from pixels in video frames other than the current frame (inter prediction) and from pixels in the same frame (intra prediction). That is, if encoded using intra frame encoding then a block, subblock or other portion of the frame (the target block or portion) is encoded relative to another block, subblock or image portion in the same frame (the reference block or portion); and if encoded using inter frame encoding then the target block or portion is encoded relative to a reference block or portion in another frame. This process is commonly referred to as prediction or prediction coding. The inter or intra prediction module will thus generate a prediction, e.g. in the form of an indication of a neighboring block or subblock in the case of intra frame encoding and/or a motion vector in the case of inter frame encoding. Typically the encoder also generates a residual signal representing a “left over” difference between the predicted block and the actual block (or predicted and actual subblocks, etc.). The residual, motion vectors and any required data associated with the intra prediction are then output into the encoded video stream, typically via further coding stages such as a quantizer and entropy encoder. Hence most blocks in the video can be encoded in terms of a difference between blocks, which requires fewer bits to encode than encoding absolute pixel values and hence saves on bitrate. Intra prediction encoding typically requires more bits than inter prediction, though still represents a saving over encoding absolute values. Details of suitable inter and intra encoding techniques for video will be familiar to a person skilled in the art.
Modern codecs allow the use of different prediction encoding modes for different portions within a frame. The possibility of having different coding options increases the rate-distortion efficiency of a video codec. The optimal coding representation has to be found for every frame region. Typically, such region is a macroblock, e.g. of 16×16 pixels. I.e. so it is possible for an intra prediction or inter prediction mode to be selected individually for each macroblock, so that different macroblocks within the same frame can be encoded with different modes. It is also possible in some codecs to use different modes based on different levels of partitioning of macroblocks, e.g. selecting between a higher complexity mode in which a separate prediction is performed for each 4×4 subblock within a macroblock or a lower complexity mode in which prediction is performed based on only 8×8 or 8×16 blocks or even whole macroblocks. The available modes may also include different options for performing prediction. For example as illustrated schematically in FIG. 1b, in one intra mode the pixels of a 4×4 subblock (b) may be determined by extrapolating down from the neighboring pixels from the subblock immediately above, or by extrapolating sideways from the subblock immediately to the left. Another special prediction mode called “skip mode” may also be provided in some codecs, which may be considered as an alternative type of inter mode. In skip mode (PSkip) the target's motion vector is inferred based on the motion vectors to the top and to the left and there is no encoding of residual coefficients. The manner in which the motion vector is inferred is consistent with motion vector prediction, thus the motion vector difference is zero and so it is only required to signal that the macroblock is a skip block.
A coding representation may thus include block partition information, prediction mode, motion vector, quantization accuracy, etc. The optimal coding option depends on video content, bit rate, earlier coding decisions, etc. The accuracy of quantization of transform coefficients is typically chosen to meet a bit rate constraint. Furthermore, distortion should be minimized.
For example, the H.264 video coder provides a great flexibility in choosing the prediction mode. For inter prediction of the luma component, a macroblock of 16×16 pixels can be represented as one block of 16×16 pixels, or two blocks of 16×8 pixels, or two blocks of 8×16 pixels, or four blocks of 8×8 pixels. Further, an 8×8 block can be represented as one block of 8×8 pixels, or two subblocks of 8×4 pixels, or two subblocks 4×8 pixels, or four subblocks of 4×4 pixels. The inter prediction is tried for each allowed partition of a macroblock. The inter prediction of a block is represented by indexing the reference frame(s) and the motion vector(s) (spatial shift from the reference block in the respective reference frame), which typically are estimated with sub-pixel precision. For intra prediction of the luma component, there are four possible modes for 16×16 blocks and nine possible modes for 4×4 subblocks. Further, there are four possible modes for chroma components. The best prediction mode is chosen by comparing the performance of inter and intra prediction modes.
The rate-distortion performance of a video codec such as H.264 AVC depends to a large extent on the performance of the macroblock mode selection o. That is, the procedure of determining whether the macroblock is best encoded, in terms of rate-distortion trade-offs, using e.g. intra mode or inter mode. From a robustness perspective, intra coded macroblocks are beneficial since they stop temporal error propagation (assuming the use of constrained intra prediction, i.e. intra prediction from inter predicted macroblocks is prohibited). However, intra coded macroblocks are generally more expensive in terms of rate compared to inter coded macroblocks, and thus it is important to introduce intra coded macroblocks systematically such that the distortion (e.g. average distortion) at the decoder is minimized given a certain bit budget and channel condition. Zhang et al., “Error resilience video coding in H.264 encoder with potential distortion tracking”, (Proc. IEEE International Conference on Image Processing, pp. 163-166, 2004) (incorporated herein in its entirety) propose such a systematic framework to introduce intra coded macroblocks based on the minimization of the expected average sum of squared differences (SSD) at the decoder. By tracking the potential distortion Zhang et al are able to compute a bias term related to the expected error-propagation distortion (at the decoder) that is added to the source coding distortion when computing the cost for inter macroblocks within the encoder rate-distortion loop.
The rate-distortion performance optimization problem can be formulated in terms of minimizing distortion under a bit rate constraint R. A Lagrangian optimization framework is often used to solve the problem, according to which the optimization criterion may be formulated as:J=D(m,o)+λR(m,o),  (1)where J represents the Lagrange function, D represents a measure of distortion (a function of mode o and macroblock m or macroblock sub-partition), R is the bitrate, and λ is a parameter defining a trade-off between distortion and rate. Commonly used distortion measures are sum of squared differences (SSD) between original and reconstructed pixels or sum of absolute differences (SAD) between the original and predicted pixels.
In this application solving the Lagrangian optimization problem means finding the encoding mode o which minimizes the Lagrange function J, where the Lagrange function J comprises at least a term representing distortion, a term representing bitrate, and a factor (the “Lagrange multiplier”) representing a tradeoff between the two. As the encoding mode o is varied towards more thorough or better quality encoding modes then the distortion term D will decrease. However, at the same time the rate term R will increase, and at a certain point dependent on λ the increase in R will outweigh the decrease in D. Hence the expression J will have some minimum value, and the encoding mode o at which this occurs is considered the optimal encoding mode.
In this sense the bitrate R, or rather the term λR, places a constraint on the optimization in that this term pulls the optimal encoding mode back from ever increasing quality. The mode at which this optimal balance is found will depend on λ, and hence λ may be considered to represent a tradeoff between bitrate and distortion.
The Lagrangian optimization is commonly used in the process of choosing coding decisions, and is applied for every frame region (e.g. every macroblock of 16×16 pixels). Commonly, the distortion may be evaluated to account for all processing stages. These include prediction, transform, and quantization. Furthermore, in order to compute reconstructed pixels, steps of inverse quantization, inverse transform, and inverse prediction must be performed. SSD is often preferred as distortion criterion since it results in higher quality compared to SAD. Commonly, the rate also accounts for coding of all needed parameters, including parameters describing prediction and quantized transform coefficients.
In Zhang et al., the authors estimate the potential distortion in the decoder due not only to source coding but also to channel errors, i.e. also a likely distortion that would be experienced due to loss of data when the signal is transmitted over the channel. The estimated potential distortion is then indirectly used to bias the mode selection towards intra coding (if there is a probability of channel errors).
Zhang's “end-to-end” distortion expression is based on the sum of squared differences (SSD) distortion measure and assumes a Bernoulli distribution for losing macroblocks.
The optimal macroblock mode oopt is given by:
                                          o            opt                    =                                    argmin              o                        ⁡                          (                                                                    D                    s                                    ⁡                                      (                                          m                      ,                      o                                        )                                                  +                                                      D                    ep_ref                                    ⁡                                      (                                          m                      ,                      o                                        )                                                  +                                  λ                  ⁢                                                                          ⁢                                      R                    ⁡                                          (                                              m                        ,                        o                                            )                                                                                  )                                      ,                            (        2        )            where Ds(m,o) denotes the SSD distortion between the original and reconstructed pixels for macroblock m and macroblock mode o, R the total rate, and λ the Lagrange multiplier relating the distortion and the rate term. Dep_ref(m,o) denotes the expected distortion within the reference macroblock in the decoder due to error propagation. Dep_ref(m,o) thus provides a bias term which bias the optimization toward intra coding if error propagation distortion becomes too large. Dep_ref(m,o) is zero for the intra coded macroblock modes. The expression Ds(m,o)+Dep_ref(m,o)+λR(m,o) may be considered an instance of a Lagrange function J. Argmino outputs the value of the argument o for which the value of the expression J is minimum.
In Zhang et al. the term Dep_ref(m,o) follows the motion of the objects and is calculated from a total distortion map using the current motion vectors. The total expected error propagation distortion map Dep is driven by the performance of the error concealment and is updated after each macroblock mode selection as:Dep(m(k),n+1)=(1−p)Dep_ref(m(k),n,oopt)+p(Dec-rec(m(k),n,oopt)+Dec-ep(m(k),n)),   (3)where n is the frame number, m(k) denotes the kth sub-partition (i.e. block or subblock) of macroblock m, p the probability of packet loss, Dec-rec denotes the SSD between the reconstructed and error concealed pixels in the encoder, and Dec-ep the expected SSD between the error concealed pixels in the encoder and decoder.
In Zhang et al. Dep is stored on a 4×4 grid over each macroblock of the frame, i.e. 16 values of Dep per macroblock, so one value of Dep per 4×4 pixel subblock of each macroblock. As shown in FIG. 1c, the computation of Dep_ref(m(k),o), i.e. the expected error-propagation reference distortion for a subblock k within the macroblock m of frame at time n, is then performed as a weighted sum of the values of Dep from four subblocks from a preceding frame from time n−1. The weights are determined from the motion vector for the block m in question. That is:
                                                        D              ep_ref                        ⁡                          (                              m                ,                                  (                  k                  )                                ,                n                            )                                =                                    ∑                              i                =                1                            4                        ⁢                                                  ⁢                                          w                i                            ⁢                                                D                  ep                                ⁡                                  (                                                                                    q                        i                                            ⁡                                              (                                                  k                          i                                                )                                                              ,                                          n                      -                      1                                                        )                                                                    ,                            (        4        )            where the weights wi are proportional to the area of overlap and where qi(ki) denotes subblock ki macroblock qi in a preceding frame n−1.
FIG. 1c provides an illustration of the computation of the expected error-propagation reference distortion from a motion vector and an expected error-propagation distortion map, with reference to exemplary subblocks b1 . . . b4 (in this example k corresponds to b1 and i counts through b1 . . . b4).